/* 前序线索二叉树 */
#include <iostream>
#include "PreThreadBiTreefun.h"
using namespace std;

// 为前序线索二叉树构建线索
void preTh(TNode *&p, TNode *&pre)
{
  // 如果结点不为空
  if (p != NULL)
  {
    // 如果当前结点没有左孩子
    if (p->lchild == NULL)
    {
      p->lchild = pre;
      p->ltag = 1;
    }
    
    // 如果前驱结点没有右孩子
    if (pre && pre->rchild == NULL)
    {
      pre->rchild = p;
      pre->rtag = 1;
    }
    
    // 记录前驱结点
    pre = p;
    
    // 为左子树构建索引
    if (p->ltag != 1)
      preTh(p->lchild, pre);
    
    // 为右子树构建索引
    if (p->rtag != 1)
      preTh(p->rchild, pre);
  }
}

// 创建前序线索二叉树
iTree create_iTree()
{
  // 接收用户输入
  char x;
  cin >> x;
  
  // 持续接收用户输入
  if (x != '#')
  {
    // 创建根结点
    TNode *T = new TNode;
    T->data = x;
    
    // 创建左子树
    T->lchild = create_iTree();
    
    // 创建右子树
    T->rchild = create_iTree();
    
    // 返回二叉树
    return T;
  }
  return NULL;
}
